N/A
N/A
Network devices such as routers must perform route lookups as part of their processing operations. A route lookup is necessary for every packet received by a router in order to determine where the packet is to be sent next. The received packets include a 32-bit wide destination address. The destination address identifies a unique address to which the packet is to be forwarded. A route lookup utilizes the destination address of the received packet in order to identify the next-hop address and exit port in a routing table. Given that the destination address is 32 bits wide, the number of possible destinations is greater than one billion. An IP address comprises a network number and a host number. The network number is of variable length and identifies a unique network. Concatenated to the network number is a host number. The host number identifies a unique host system within a particular network. A received network number part of the address is matched with multiple entries in a routing table to identify the best match. The best match is the one with the largest matching number of bits in the first part in the address. Known methods used to perform this matching are complicated and can take a long time. It would be desirable to provide a route lookup engine which can perform a route lookup quickly and efficiently.
A Route Lookup Engine (RLE) for determining a next hop index is disclosed. The RLE receives a lookup key and performs a multi-bit trie search with prefix expansion and capture of a variable stride trie. The data that the RLE returns comprises the next hop information and status flags. The RLE uses a compact, field reusable data structure. The RLE performs both unicast and multicast IP address lookups on Virtual Private Networks. The RLE uses separate indexing and forwarding memories. The upper bound of the search time for the RLE is fixed regardless of the route table size.